package com.atguigu.ds.impl;

import com.atguigu.DynamicArray;
import com.atguigu.ds.Map;

import java.util.function.BiConsumer;

public class HashTable<K,V> implements Map<K,V> {

    private Node<K,V>[] arr = new Node[4];

    private final static Double Load_Factor = 0.75 ;

    private static class Node<K,V>{
        K key ;
        V value ;
        Node<K,V> next ;

        Node(K key , V value , Node<K,V> next){
            this.key = key;
            this.value = value ;
            this.next = next ;
        }
    }

    private int size ;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void put(K key, V value) {
        //int hash = Math.abs(key.hashCode()) %2000;
        int hash = hash(key,arr.length);
        Node<K,V> node = null ;
        if(arr[hash]==null){//说明这个位置上一个元素都没有，则我们可以将当前节点作为头结点
            node = new Node<>(key,value,null);
        }else{
            Node curr = arr[hash];
            while(curr!=null){
                if(curr.key.equals(key)){
                    curr.value = value;
                    return ;
                }
                curr = curr.next;
            }
            node = new Node<>(key,value,arr[hash]);
        }
        arr[hash] = node ;
        size++;

        //如果 数量除以数组的长度等于增长因子，则扩容
        if((double)size/arr.length>Load_Factor){
            grow();
        }
    }

    private void grow(){
        Node<K,V>[] arr2 = new Node[arr.length*2];
        for(int i = 0 ; i<arr.length ; i++){
            //取出某一个索引位置上的头结点
            Node<K,V> node = arr[i];        //a
            while(node!=null){
                //在a节点操作之前，先记录a节点后续节点的引用，否则一会儿就覆盖丢失了
                Node<K,V> nodeNext = node.next;

                int hash2 = hash(node.key,arr2.length);
                node.next = arr2[hash2];
                arr2[hash2] = node ;

                node = nodeNext ;
            }
        }
        arr = arr2 ;
    }

    private int hash(K key , int length){
        return key.hashCode()&Integer.MAX_VALUE % length ;
    }

    @Override
    public V get(K key) {
        int hash = hash(key,arr.length);
        Node<K,V> curr = arr[hash];
        while(curr!=null){
            if(curr.key.equals(key)){
                return curr.value;
            }
            curr = curr.next ;
        }
        return null;
    }

    @Override
    public V remove(K key) {
        int hash = hash(key,arr.length);
        Node<K,V> header = arr[hash];
        if(header==null){
            return null ;
        }else{
            if(header.key.equals(key)){
                arr[hash] = header.next ;
                size--;
                return header.value;
            }else{
                Node<K,V> curr = header.next;
                Node<K,V> pre = header ;
                while(curr!=null){
                    if(curr.key.equals(key)){
                        pre.next = curr.next;
                        size--;
                        return curr.value;
                    }
                    pre = curr ;
                    curr = curr.next ;
                }
            }
        }
        return null;
    }

    @Override
    public void forEach(BiConsumer<K, V> consumer) {

    }
}
